package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/6/12 10:58
 */
public class C1449 {

    public static int largestNumber(int[] cost, int target) {
        return process(cost, 0, target);
    }

    public static int process(int[] cost, int i, int rest) {
        if (i == cost.length) return rest == 0 ? 0 : Integer.MIN_VALUE;
        int max = 0;
        for (int j = 0; j * cost[i] <= rest; j++) {
            max = Math.max(max, (i + 1) * j + process(cost, i + 1, rest - j * cost[i]));
        }
        return max;
    }

    public static int cache(int[] cost, int target) {
        Integer[][] dp = new Integer[cost.length + 1][target + 1];
        int ans = process2(cost, 0, target, dp);
        for (Integer[] nums : dp) {
            for (int i = 0; i < nums.length; i++) {
                System.out.print(nums[i] + " ");
            }
            System.out.println();
        }
        return ans;
    }

    private static int process2(int[] cost, int i, int rest, Integer[][] dp) {
        if (dp[i][rest] != null) return dp[i][rest];
        int ans = 0;
        if (i == cost.length) {
            ans = rest == 0 ? 0 : Integer.MIN_VALUE;
        } else {
            int max = 0;
            for (int j = 0; j * cost[i] <= rest; j++) {
                max = Math.max(max, (i + 1) * j + process(cost, i + 1, rest - j * cost[i]));
            }
            ans = max;
        }
        return dp[i][rest] = ans;
    }


    // for test
    public static void main(String[] args) {
        int[] cost = {4, 3, 2, 5, 6, 7, 2, 5, 5};
        int target = 9;
        System.out.println(largestNumber(cost, target));
        System.out.println(cache(cost, target));
    }

}
